/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {
    const res = [];
    const map = {};

    for (const ticket of tickets) { // 建表
        const [from, to] = ticket;
        if (!map[from]) {
            map[from] = [];
        }
        map[from].push(to);
    }
    for (const city in map) {
        map[city].sort();
    }
    console.log(map)

    const dfs = (node) => { // 当前城市
        const nextNodes = map[node]; // 当前城市的邻接城市
        // 第一次循环就把map后的arr全都shift出去了
        while (nextNodes && nextNodes.length) { // 遍历，一次迭代设置一个递归分支
            const next = nextNodes.shift(); // 获取并移除第一项，字母小的城市
            dfs(next);                      // 向下递归
        }
        // 当前城市没有下一站，就把他加到res里，递归开始向上返回，选过的城市一个个推入res 
        res.unshift(node);
    };

    dfs('JFK'); // 起点城市
    return res;
};

  

// 输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
// 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
// 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
// 下面两种方法全部超时




var findItinerary = function(tickets) {
    let result = ['JFK']
    let map = {}

    for (const tickt of tickets) {
        const [from, to] = tickt
        if (!map[from]) {
            map[from] = []
        }
        map[from].push(to)
    }

    for (const city in map) {
        // 对到达城市列表排序
        map[city].sort()
    }
    function backtracing() {
        if (result.length === tickets.length + 1) {
            return true
        }
        if (!map[result[result.length - 1]] || !map[result[result.length - 1]].length) {
            return false
        }
        for(let i = 0 ; i <  map[result[result.length - 1]].length; i++) {
            let city = map[result[result.length - 1]][i]
            // 删除已走过航线，防止死循环
            map[result[result.length - 1]].splice(i, 1)
            result.push(city)
            if (backtracing()) {
                return true
            }
            result.pop()
            map[result[result.length - 1]].splice(i, 0, city)
        }
    }
    backtracing()
    return result
};





/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {
    let res = [],
        visitArr = new Array(tickets.length - 1).fill(false);
    findItineraryEvery(tickets, ["JFK"], res, visitArr)
    return res
};
function findItineraryEvery(tickets, valArr, res, visitArr) {
    console.log(valArr)
    if (valArr.length > tickets.length + 1) return
    if (valArr.length === tickets.length + 1) {
        res.push([...valArr])
        return
    }

    for (let i = 0; i < tickets.length; i++) {
        if (visitArr[i]) {
            continue
        }
        if (tickets[i][0] === valArr[valArr.length - 1]) {
            valArr.push(tickets[i][1])
            visitArr[i] = true
            findItineraryEvery(tickets, valArr, res, visitArr)
            valArr.pop()
            visitArr[i] = false
        }
    }
}